package com.lie.prepare.algorithm.sort;

import java.util.Arrays;
import java.util.Random;
import static com.lie.prepare.util.Print.*;

/**
 * Created by lie on 2018/4/12.
 * 插入排序（这里讲直接插入排序）
 * 好像拿到一手扑克牌的排序手段：
 *  摸到两张，排序
 *  再摸一张，再排序
 *  如此反复
 *
 *  时间复杂度和冒泡{@link BubbleSort}一样，都是O(n^2)
 *
 *  插入的话（像打牌一样，每次摸牌进行排序）
 *  举个例子，{8, 5, 3}
 *  起手是8，
 *  摸到5
 *  temp= 5, {8 , 8} ,{5, 8}
 *  摸到3
 *  temp=3, {5, 8, 8} ,{5, 5, 8}{3, 5, 8}
 *
 *  尽管时间复杂度并不高，不过这里关于temp的处理挺好玩
 *  不要拘泥于temp只是写{@link BubbleSort#swap(int[], int)}这种的操作
 *
 *  插入排序是稳定的
 */
public class InsertSort {
    private static Random random = new Random(47);

    public static int[] directInsert(int[] array){

        for (int i = 1; i < array.length; i++) {
            int index = i - 1 ;
            //起手已经有一张牌，i=0
            //temp是新摸上来的牌,i+1
            int temp = array[i];//注意到这里已经把新摸上来的牌进行了缓存

            while (index >=0 && temp< array[index]){

                array[index + 1] = array[index];
                --index;
            }
            //此时的index是最后一次进行替换的现场 补加1
            array[index + 1] = temp;
        }
        return array;
    }

   public static int[] generateData(){
       int[] ints = new int[10];
       for (int i = 0; i < ints.length; i++) {
           ints[i] = random.nextInt(10);
       }
       return ints;
   }

   public static void main(String[] args){
       int[] data = generateData();
       print("排序之前 "+ Arrays.toString(data));//排序之前 [8, 5, 3, 1, 1, 9, 8, 0, 2, 7]
       int[] dataAfterSort = directInsert(data);
       print("排序之后 "+ Arrays.toString(dataAfterSort));
   }
}
